package practice.sort.compare;

import practice.sort.Sort;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/8/9 20:39
 */
public class MergeSort extends Sort {
    int[] leftArray;
    @Override
    public void sort() {
        leftArray = new int[nums.length >> 1];
        sort(0, nums.length - 1);
    }

    public void sort(int left, int right) {
        if (left >= right) return;
        int mid = left + ((right - left) >> 1);
        sort(left, mid);
        sort(mid + 1, right);
        merge(left, mid, right);
    }

    public void merge(int left, int mid, int right) {
        for (int i = 0; i < mid - left + 1; i++) {
            leftArray[i] = nums[left + i];
        }
        int li = 0;
        int le = mid - left;
        int ri = mid + 1;
        int ni = left;
        while (li <= le) {
            if (ri <= right && nums[ri] < leftArray[li]) {
                nums[ni++] = nums[ri++];
            } else {
                nums[ni++] = leftArray[li++];
            }
        }
    }
}
